# -*- coding: utf-8 -*-

"""剑指 Offer II 016. 不含重复字符的最长子字符串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

示例 1:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子字符串是 "b"，所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:
输入: s = ""
输出: 0

提示：
0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成"""


from typing import AsyncIterable


class Solution:
    """因为一个字串中间字符无重复，要扩展字串，可以用双指针，tail指针只能往后。
    同时，为了提升效率，头尾指针间可以维系一个哈希字典表，key为字符，val为位置，当尾指针探测到重复字符时，头指针直接跳到当前字串中重复字符后一位"""
    def lengthOfLongestSubstring(self, s: str) -> int:
        head, tail = 0, 0
        table = {}
        longest = 0
        size = 0
        while True:
            try:
                if tail < head:
                    tail = head

                if s[tail] in table.keys():
                    # print(s[tail], tail, table)
                    p = table[s[tail]]
                    for i in range(head, p+1):
                        table.pop(s[i])
                    head = p+1

                    size = tail-head+1

                    table[s[tail]] = tail
                    tail += 1
                else:
                    size += 1
                    if size > longest:
                        longest = size
                    
                    table[s[tail]] = tail
                    tail += 1
            except IndexError:
                break
        return longest


if __name__ == '__main__':
    so = Solution()
    print(so.lengthOfLongestSubstring('abcabcbb'))
    print(so.lengthOfLongestSubstring('bbbbb'))
    print(so.lengthOfLongestSubstring('pwwkew'))
    print(so.lengthOfLongestSubstring(''))
